%!TEX root = verifiableLeakage.tex

\subsection{Leakage Models}
In this section we focus on memory leakage models, we briefly review circuit leakage models in \apref{sec:circuit leakage}.  Our results are in this area. 
\label{sec:leakage models}
\paragraph{Bounded Leakage:}  This is the original leakage function introduced by Micali and Reyzin~\cite{DBLP:conf/tcc/MicaliR04}.  It argues for leakage functions where the overall length is bounded:
\begin{definition}
Let $K$ be a discrete random variable over space $\mathcal{M}$.  The randomized map $\mathcal{L}:\mathcal{M}\rightarrow \zo^*$ is an $\ell$-bounded leakage function if for $\mathcal{L}(x)$ takes at most $2^\ell$ values for any choice $x\in\mathcal{M}$ and any choice of random coins of $\mathcal{L}$.  
\end{definition}
Bounded leakage is a natural definition to work with.  If a random variables starts with min-entropy $k$, we know that after $\ell$ bits of leakage it has remaining min-entropy $k-\ell$~\cite[Lemma 2.2]{DBLP:journals/siamcomp/DodisORS08}.  That is, if $\Hoo(K)\geq k$, then $\Hav(K| L(K))\geq k-\ell$.  Unfortunately, most leakage does not fit into this model.  Using our example, power traces contain a considerable amount of information and typically take values in a very large universe~(larger than the key itself).

\paragraph{Indistinguishable Leakage} The notion of indistinguishable leakage was introduced as a minimum condition for leakage~(it has since been weakened by hard to invert leakage, see below).  The hope is that secret state should look  as though it has entropy conditioned on leakage~(even if it is information-theoretically determined).  Dziembowski and Pietrzak construct a pseudorandom generator secure against this type of leakage~\cite{DBLP:conf/focs/DziembowskiP08}.  We begin by describing indistinguishability from high entropy random variables~(the notion was introduced by Hastad et al.~\cite{DBLP:journals/siamcomp/HastadILL99} and extended to the conditional setting by Hsiao et al~\cite{DBLP:conf/eurocrypt/HsiaoLR07}).

\begin{definition}
\label{def:hill entropy}
Let $(K, Y)$ be a pair of random variables.  $K$ has 
\emph{relaxed HILL entropy} at least $k$ conditioned on $Y$,
denoted $H^{\hill}_{\epsilon, s_{sec}}(K|Y)\geq k$ if for each $y\in Y$ there exists $Z_y$ giving rise to a joint distribution $(Z, Y)$, such that $\Hav(Z|Y)\geq k$ and $\delta^{\mathcal{D}_{s_{sec}}} (K,Y),(Z,Y))\leq \epsilon$.
\end{definition}

We then define indistinguishability leakage as one that retains high HILL entropy

\begin{definition}
\label{def:indist leakage}
Let $K$ be a random variable and let $\mathcal{L}$ be a randomized map.  $\mathcal{L}$ is a $(k, \epsilon, s_{sec})$-indistinguishable leakage function if $H^{\hill}_{\epsilon, s_{sec}}(K | \mathcal{L}(K)) \geq k$.
\end{definition}
\paragraph{Hard to invert leakage} For a scheme with secret key $K$, the minimal notion of security is that an adversary should not be able to predict the value of $K$.  This is model is known as the auxiliary input~\cite{dodis2009cryptography} or hard-to-invert leakage~\cite{faust2012signature}.  We recall the definition of unpredictability entropy from Hsaio, Lu, and Reyzin~\cite{DBLP:conf/eurocrypt/HsiaoLR07}
\begin{definition}
\label{def:unp entropy}
Let  $(K, Y)$ be a pair of random variables. We say that $K$ has \emph{unpredictability entropy} at least $k$ conditioned on $Y,$ denoted by $H^{\unp}_{\epsilon, s_{sec}} (K|Y) \geq k$, if for all joint distributions $(Z, Y)$ such that $\delta^{\mathcal{D}_{s_{sec}}}((K, Y),(Z, Y))\leq \epsilon$, and for all circuits $\mathcal{I}$ of size $s_{sec}$,
\[
\Pr[\mathcal{I}(Y) = Z ] \leq 2^{-k}
.\]
\end{definition}
\noindent
We now present the definition of a hard to invert leakage function:
\begin{definition}
Let $K$ be a random variable over space $\mathcal{M}$.  The randomized map $\mathcal{L}$ is a $(k, \epsilon, s_{sec})$-\emph{hard-to-invert leakage} if $H^{\unp}_{\epsilon, s_{sec}}(K| \mathcal{L}(K))\geq k$.
\end{definition}
Note that we make no condition in the above definition about $K$ unconditionally.  For $K$ to be unpredictable with $\mathcal{L}(K)$ it must be at least $k$ unpredictable by polynomial time algorithms.  If we consider the non-uniform setting this ensures that $\Hoo(K)\geq k$.  While unpredictability seems like the weakest possible definition~(and thus the strongest possible set of leakage functions), we do not have complete results for this definition.  In particular, we do not have schemes with security against multiple hard-to-invert leakage functions.

\section{Simulatable Leakage} 
\label{sec:sim leakage}
Standaert, Pereira, and Yu~\cite{standaertleakage} introduce a new class of leakage functions designed to be achievable and verifiable.   Simulatable leakage is leakage can be simulated without access to the true secret state.  Intuitively, this type of leakage should not be useful to an adversary as they can simulate the leakage on their own.  We first present the definition of Standaert, Pereira, and Yu~\cite{standaertleakage}.  
\begin{table}[ht] 
%\caption{Nonlinear Model Results} % title of Table 
\centering % used for centering table 
\begin{tabular}{| c | c | c |} % centered columns (4 columns) 
\hline\hline %inserts double horizontal lines 
\multicolumn{3}{| c |}{Game $q-sim(\mathcal{A},BC,L,\mathcal{S},b)$.} \\
\hline
\multicolumn{3}{| l |}{The challenger selects two random keys $k$ and $k^*$ in $\zo^n$.  The output of}\\
\multicolumn{3}{| l |}{the game is a bit $b'$ computed by $\mathcal{A}^L$ based on the challenger responses}\\
\multicolumn{3}{| l |}{to a total of at most $q$ adversarial queries of the following type:}\\
\hline
Query & Response if $b=0$ & Response if $b=1$ \\ [0.5ex] \hline
$Enc(x)$ & $BC_k(x), L(k, x)$ & $BC_k(x), \mathcal{S}^L(k^*, x, BC_k(x))$ \\\hline 
\multicolumn{3}{| l |}{and one query of the following type:}\\
\hline
Query & Response if $b=0$ & Response if $b=1$ \\
$Gen(z, x)$ & $\mathcal{S}^L(z, x, k)$ & $\mathcal{S}^L(z, x, k^*)$\\
\hline %inserts single line 
\end{tabular} 
\label{qsimGame}
\end{table} 


\begin{definition}~\cite[Definition 1]{standaertleakage}
\label{def:old sim leakage}
A block cipher $BC$ with leakage function $L$ has $(s_{sim}, t_{sim}, s_{\mathcal{A}}, t_{\mathcal{A}}, \epsilon)$ $q$-simulatable leakages if there is an $(s_{sim}, t_{sim})$-bounded simulator $\mathcal{S}^L$ such that, for every $(s_{\mathcal{A}}, t_{\mathcal{A}})$-bounded adversary $\mathcal{A}^l$, we have:
\[
|\Pr[q-sim(\mathcal{A}, BC, L, S^L, 1) = 1] - \Pr[q-sim(\mathcal{A}, BC, L, \mathcal{S}^L, 0) = 1] | \le \epsilon.
\].
\end{definition}
\subsection{Extending Simulatable leakage to general applications}
\defref{def:old sim leakage} is specialized to the setting of symmetric-key cryptography.  In particular, the second type of query exists because the authors argue that symmetric keys are often derived from sources that themselves have leakage.  It is not clear how to generalize this type of query to arbitrary leakage settings.  In addition, providing a single key to $\mathcal{S}$ as consistent state seems rather limiting, it is not clear why the simulator should not be allowed to keep state between leakage queries.  Furthermore, the fact that leakage is provided with each output of the block cipher is not a necessary requirement.  There may multiple leakage queries for each block cipher output or vice versa.  We present a general definition here.

\begin{definition}  
\label{def:sim leakage}
Let $(K, Y)$ be a pair of random variables.  The randomized map $\mathcal{L}$ is an $(\epsilon, s_{sim}, s_{sec})$-\emph{simultable leakage function} if there exists a simulator $S$ of size at most $s_{sim}$ such that 
\[
\delta^{\mathcal{D}_{s_{sec}}}\left((Y, \mathcal{L}(K)), (Y, S(Y))\right)\leq \epsilon.
\]
\end{definition}

\textbf{Notes:} Neither \defref{def:old sim leakage} or \defref{def:sim leakage} incorporate secret key updates, thus we can effectively model multiple leakage queries $\mathcal{L}_1, \mathcal{L}_2$ as a single leakage query $\mathcal{L}$.  The main difference~(assuming the simulator $S$ is allowed to keep state between queries) is that the simulator is able to ``anticipate'' future queries and thus prepare their response in a consistent manner.  Where possible we assume a single leakage query for clarity.  We assume that $Y$ incorporates all public values of the scheme.  This may include a public-key, ciphertexts, signatures, etc.  In the work of Standaert et al., this is assumed to be the input and output of the block cipher with the true key.

%\defref{def:sim leakage} extends to multiple leakage functions~(a crucial question is whether the simulator is allowed to keep state between leakage queries, this seems necessary and is allowed by Standaert, Pereira, and Yu~\cite{standaertleakage}).

Simulatable leakage does not imply security of the underlying cryptographic scheme.  Consider a private key $K$ over some domain.  If the condition $Y$ is empty, the leakage $\mathcal{L}(K) = K$ is simulatable by sampling a fresh secret key $K'$.  However, there is no security remaining in the system.  In particular, in this setting, there is no min-entropy, HILL entropy, or unpredictability entropy remaining in the key.  This holds for any polynomial time function $f$ by first sampling a fresh $k\leftarrow K$ and then outputting $f(k)$.  This gives us the following lemma:
\begin{lemma}~\label{lem:resample possible}
Let $K$ be a random variable over $\mathcal{M}$ samplable by procedure $\sample$ of size $s_{sam}$.  Let $f:\mathcal{M}\rightarrow \zo^*$ be a function.  Then $f$ is a $(0, s_{sim}, \infty)$-simulatable leakage if $s_{sim}\geq |f| + s_{sam}$.  In particular, when $f(x) = x$ then $\Hav(K|f(K)) = H^{\hill}(K|f(K)) = H^{\unp}(K|f(K)) = 0$.
\end{lemma}
\textbf{Note:} This type of leakage is implicitly prohibited by in \defref{def:old sim leakage} because each leakage query has a ciphertext output.  If $BC$ is secure it is computationally hard to find a fresh key that is consistent on the plaintext/ciphertext pair (for most block ciphers no such key exists).

It is not just empty $Y$ that presents a problem to simulatable leakage.  It may be possible to leak the entire secret even when it is information-theoretically determined by the condition $Y$.  \

\bnote{maybe exclude this example, seems like more trouble than it is worth.}  We first note the decision Diffie-Hellman assumption~\cite{boneh1998decision}.

\begin{assumption}[Decisional Diffie-Hellman]
Let $G$ be a cycle group of order $q$.  Let $A, B, C$ be uniformly sampled random variables from $\mathbb{Z}_q$.  The following holds:
\[
\delta^{\mathcal{D}_{s_{sec}}}((g^A, g^B, g^{A*B}), (g^A, g^B, g^C))\leq \epsilon.
\]
\end{assumption}
\begin{lemma}
If the decisional Diffie-Hellman assumption holds for some group~(with hardness $\epsilon, s_{sec}$), then for $K = g^{AB}, Y=(g^A, g^B)$,  $\mathcal{L}(K) = K$ is a $(\epsilon, |G|, s_{sec})$-simulatable leakage.
\end{lemma}
\begin{proof}
Suppose not, that is for all simulators of size $|G|$ there exists a distinguisher $D$ that distinguishes $Y = (g^A, g^B), \mathcal{L}(K) = g^{AB}$ from $Y, S(Y)$.  Let $S$ be the simulator that samples a uniformly random element of $g^C$.  $D$ breaks the decisional Diffie-Hellman assumption.
\end{proof}
\noindent To prevent these \emph{leak-and-resample} simulators, we consider the setting where there is a some public verification procedure for the ``correct'' $K$.  We use the notation of witness hiding from zero-knowledge.

\begin{definition}
Let $K, Y$ be a joint random variable and let $R$ be a relation~(computable by a circuit of size $s_{rel}$) where $\Pr[R(K, Y) = 1]=1$.  The public state $Y$ is a $(s_{rel}, s_{inv}, \epsilon_{rel})$-\emph{witness hiding relation} if for all $\mathcal{I}_{s_{inv}}, \Pr[R(\mathcal{I}(Y), Y) = 1]\le \epsilon_{rel}$.
\end{definition}

For the remainder of the discussion, we will consider public information that is witness hiding of the secret state $K$.  As stated, above simulatable leakage is not meaningful if the simulator can ``invert'' the public state to create a plausible private state.

\begin{lemma}
Witness hiding implies unpredictability.  Containment is tight.
\end{lemma}

\bnote{need to talk about how this is stronger than unpredictability as it implies that we can check whether an answer is right}
